\subsubsection{std::map и std::set}
\myindex{\Cpp!STL!std::map}
\myindex{\Cpp!STL!std::set}
\myindex{Двоичное дерево}

Двоичное дерево---это еще одна фундаментальная структура данных.
Как следует из названия, это дерево, но у каждого узла максимум 2 связи с другими узлами.
Каждый узел имеет ключ и/или значение:
в \TT{std::set} у каждого узла есть ключ,
в \TT{std::map} у каждого узла есть и ключ и значение.

Обычно, именно при помощи двоичных деревьев реализуются \q{словари} пар ключ-значения 
(\ac{AKA} \q{ассоциативные массивы}).

Двоичные деревья имеют по крайней мере три важных свойства:

\begin{itemize}
\item Все ключи всегда хранятся в отсортированном виде.
\item Могут хранится ключи любых типов.
Алгоритмы для работы с двоичными деревьями не зависят от типа ключа,
для работы им нужна только функция для сравнения ключей.
\item Поиск заданного ключа относительно быстрый по сравнению со списками или массивами.
\end{itemize}

Очень простой пример: давайте сохраним вот эти числа в двоичном дереве:
0, 1, 2, 3, 5, 6, 9, 10, 11, 12, 20, 99, 100, 101, 107, 1001, 1010.

\input{\CURPATH/STL/map_set/example_tikz}

Все ключи меньше чем значение ключа узла, сохраняются по левой стороне.
Все ключи больше чем значение ключа узла, сохраняются по правой стороне.

Таким образом, алгоритм для поиска нужного ключа прост: если искомое значение меньше чем значение текущего узла:
двигаемся влево, если больше: двигаемся вправо, останавливаемся если они равны.
Таким образом, алгоритм может искать числа, текстовые строки, итд, 
пользуясь только функцией сравнения ключей.

Все ключи имеют уникальные значения.

Учитывая это, нужно $\approx \log_{2} n$ шагов для поиска ключа 
в сбалансированном дереве, содержащем $n$ ключей.
Это $\approx 10$ шагов для $\approx 1000$ ключей, или $\approx 13$ 
шагов для $\approx 10000$ ключей.
Неплохо, но для этого дерево всегда должно быть сбалансировано: т.е. ключи должны быть равномерно распределены
на всех ярусах.
Операции вставки и удаления проводят дополнительную работу по обслуживанию дерева и сохранения его в сбалансированном
состоянии.

Известно несколько популярных алгоритмом балансировки, включая AVL-деревья и красно-черные деревья.
Последний дополняет узел значением \q{цвета} для упрощения балансировки, таким образом каждый узел может быть
\q{красным} или \q{черным}.

Реализации \TT{std::map} и \TT{std::set} обоих GCC и MSVC используют красно-черные деревья.

\TT{std::set} содержит только ключи.
\TT{std::map} это \q{расширенная} версия set: здесь имеется еще и значение (value) на каждом узле.

\myparagraph{MSVC}

\lstinputlisting[style=customc]{\CURPATH/STL/map_set/MSVC_RU.cpp}

\lstinputlisting[caption=MSVC 2012]{\CURPATH/STL/map_set/MSVC.txt}

Структура не запакована, так что оба значения типа \Tchar занимают по 4 байта.

В \TT{std::map}, \TT{first} и \TT{second} могут быть представлены как одно значение типа \TT{std::pair}.
\TT{std::set} имеет только одно значение в этом месте структуры.

Текущий размер дерева всегда присутствует, как и в случае реализации \TT{std::list} в MSVC (\myref{MSVC_std_list}).

Как и в случае с \TT{std::list}, итераторы это просто указатели на узлы.
Итератор \TT{.begin()} указывает на минимальный ключ.
Этот указатель нигде не сохранен (как в списках), минимальный ключ дерева нужно находить каждый раз.
\TT{operator--} и \TT{operator++} перемещают указатель не текущий узел на узел-предшественник
или узел-преемник, т.е. узлы содержащие предыдущий и следующий ключ.
Алгоритмы для всех этих операций описаны в
[Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford,
\IT{Introduction to Algorithms, Third Edition}, (2009)].

Итератор \TT{.end()} указывает на узел-пустышку, он имеет 1 в \TT{Isnil}, что означает, что у узла
нет ключа и/или значения.

Так что его можно рассматривать как \q{landing zone} в \ac{HDD}.
Этот узел часто называется \IT{sentinel} [см. N. Wirth, \IT{Algorithms and Data Structures}, 1985]
\footnote{\url{http://www.ethoberon.ethz.ch/WirthPubl/AD.pdf}}.

Поле \q{parent} узла-пустышки указывает на корневой узел, который служит
как вершина дерева, и уже содержит информацию.

\myparagraph{GCC}

\lstinputlisting[style=customc]{\CURPATH/STL/map_set/GCC.cpp}

\lstinputlisting[caption=GCC 4.8.1]{\CURPATH/STL/map_set/GCC.txt}

Реализация в GCC очень похожа
\footnote{\url{http://go.yurichev.com/17084}}.
Разница только в том, что здесь нет поля \TT{Isnil},
так что структура занимает немного меньше места в памяти чем та что реализована в MSVC.

Узел-пустышка --- это также место, куда указывает итератор \TT{.end()}, не имеющий ключа и/или значения.

\myparagraph{Демонстрация перебалансировки (GCC)}

Вот также демонстрация, показывающая нам как дерево может перебалансироваться после вставок.

\lstinputlisting[caption=GCC,style=customc]{\CURPATH/STL/map_set/GCC_rebalancing_demo.cpp}

\lstinputlisting[caption=GCC 4.8.1]{\CURPATH/STL/map_set/GCC_rebalancing_demo.txt}

